Home | | Latest | About | Random
# 39 Application to linear recurrences.
Let us now see an application of diagonalization in studying a linear recurrence. Before we start, let me remind you that if a square matrix $A$ is diagonalizable, then its powers are easy to compute. Indeed, if we have diagonalization $A = PDP^{-1}$, then $A^{n}=PD^{n}P^{-1}$.
## Linear recurrences.
A sequence of numbers $(a_{n})_{n=0}^{\infty} = (a_{0},a_{1},a_{2},\ldots)$ is said to satisfies an **$k$-th order linear recurrence** if each term of the sequence depends on some linear combination of the immediate previous $k$ many terms, and with the first $k$ terms some specified initial conditions. That is, we have $$
\begin{array}{ll}
\text{some fixed initial values } a_{0},a_{1},\ldots ,a_{k-1}, \\
a_{n+k} = c_{0} a_{n} + c_{1} a_{n+1} +c_{2}a_{n+2}+ \cdots c_{k-1}a_{n+k-1} & \text{for all \(n \ge 0\)}
\end{array}
$$for some fixed constants $c_{0},c_{1},\ldots,c_{k-1}$.
For example, the classic Fibonacci sequence $(a_{n})$ satisfies the 2nd order linear recurrence $$
\begin{array}{l}
a_{0} = 0, a_{1} = 1 \\
a_{n+2} = a_{n}+a_{n+1}
\end{array}
$$Let me remark that one could choose a different set of initial conditions, and you will get another Fibonacci like sequence.
These are called linear recurrences because each term depends on a _linear combination_ of the $k$ _immediate previous_ terms. So you have to be careful in determining the order. For instance, $$
a_{n+5} = 5a_{n}-2a_{n+3}
$$is actually an order 5 linear recurrence, since $a_{n+5}$ depends on a linear combination of $a_{n},a_{n+1},a_{n+2},a_{n+3},a_{n+4}$, with some of the coefficients zero.
Let us look at some of the terms of the Fibonacci sequence $(a_n)_{n=0}^{\infty}$ with $a_{0}=0,a_{1}=1$ and $a_{n+2}=a_{n}+a_{n+1}$, we have $$
\begin{array}{c|ccccccc}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \cdots & 1000\\ \hline
a_{n} & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & \cdots &???
\end{array}
$$
Certainly one can compute the $1000$-th term of the sequence using the rule. But naively to do that we need to know the $999$-th term as well as the $998$-th term, and to know those we need the $997$-th term and $996$-th term, and.... so on. In principle, the recurrence defines a well-defined sequence, but there are some questions that we would like to know:
- Can we find a _closed form formula_ for the term $a_{n}$? That is, can we write down some expression using simple functions (like basic arithmetic functions, powers, roots, etc) that can give a better sense of what $a_{n}$ equals to?
- Just _how big_ is $a_{1000}$? Or more generally,
- How does $a_{n}$ grow _asymptotically_? That is, can we find a simple function $f(n)$ such that $a_{n}\sim f(n)$?
## Asymptotic relation -- a detour discussion.
Note, here $\sim$ is read as _"asymptotic to"_, and if we write $a_{n}\sim f(n)$ we mean $$
\lim_{n\to\infty} \frac{a_{n}}{f(n)} = 1.
$$In other words, $a_{n}$ and $f(n)$ behaves _essentially the same, in the large limit of $n$_. This gives a better sense of $a_{n}$, at least when $n$ is large. Finding asymptotic relations allows us to simplify otherwise more complicated functions, if we only care about large $n$ limit behavior. For example, the function $$
f(n) = 4 n^{7}-3n^{3}+n^{2}+6\sin(3n) - \frac{21}{n^{2}}
$$is asymptotic to $4n^{7}$, because the limit $$
\begin{align*}
\lim_{n\to\infty} \frac{f(n)}{4n^{7}} & =\lim_{n\to\infty} \frac{4n^{7}-3n^{3}+n^{2}+6 \sin(3n)-\frac{4}{n^{2}}}{4n^{7}} \\
& = \lim_{n\to\infty} 1 - \frac{3}{4n^{4}} +\frac{1}{4n^{5}}+ \frac{6\sin(3n)}{4n^{7}} - \frac{21}{4n^{9}} \\
& =1
\end{align*}
$$So $f(n) \sim 4n^{7}$, and in the large $n$ limit, it is easier to think about $f(n)$ as the function $4n^{7}$ behaviorally, even though they are not the same functions. We are able to replace something more complicated with something simple.
A famous asymptotic relation is the _prime number theorem_, where $\pi(n) \sim \frac{n}{\log n}$. Here $\pi(n)$ is the number of prime numbers less than $n$. To determine the exact number of primes or know how they are actually distributed is a difficult task, but miraculously we have a simple asymptotic relation! It is one of the greatest stories (and on-going) of mathematics.
Also, you may have noticed we used a _squiggle_ $\sim$ to denote asymptotic relation here, which might remind you of $\stackrel{\text{row}}\sim$ and $\stackrel{\text{sim}}\sim$. Now asymptotic relation has nothing to do with matrices per se, but it is an _equivalence relation_ on functions! I leave that for you to verify the details.
Let us get back to our linear recurrence business.
## A case study: Fibonacci sequence.
As a case study, let us investigate the Fibonacci sequence $(a_{n})_{n=0}^{\infty}$ given by $$
\begin{array}{}
a_{0} = 0, a_{1} = 1 \\
a_{n+2} = a_{n} + a_{n+1}
\end{array}
$$
We will answer the following:
- Find a _close form formula_ for $a_{n}$.
- What is the first digit of $a_{1000}$, and how many digits are in $a_{1000}$?
- What is a simple asymptotic form for $a_{n}$?
We will solve it with linear algebra methods as follows.
### Encode the sequence as a sequence of vectors.
Our Fibonacci sequence is a 2nd order linear recurrence, so let us define a sequence of $2\times 1$ vectors $$
\vec x_{n} = \begin{pmatrix}a_{n} \\ a_{n+1}\end{pmatrix}
$$
that captures 2 consecutive terms of the sequence. So we have $$
\vec x_{0} = \begin{pmatrix}a_{0}\\a_{1}\end{pmatrix}, \vec x_{2} = \begin{pmatrix}a_{1}\\a_{2}\end{pmatrix},\vec x_{3} = \begin{pmatrix}a_{3}\\a_{4}\end{pmatrix},\ldots
$$
### Encode the recurrence relation as a matrix multiplication map.
For our sequence of vectors $\vec x_{n}$ that we just defined, let us find a relation between $\vec x_{n}$ and $\vec x_{n+1}$. Notice that $$
\vec x_{n+1} = \begin{pmatrix}a_{n+1}\\a_{n+2}\end{pmatrix} = \begin{pmatrix}a_{n+1}\\a_{n} +a_{n+1}\end{pmatrix} = \begin{pmatrix}0 & 1\\1 & 1\end{pmatrix} \begin{pmatrix}a_{n}\\a_{n+1}\end{pmatrix} = \begin{pmatrix}0 & 1\\1 & 1\end{pmatrix}\vec x_{n}
$$This gives a _recurrence_ on the sequence of vectors $\vec x_{n}$ itself! If we write the matrix here as $A$, then $$
\begin{array}{l}
\vec x_{1} = A \vec x_{0} \\
\vec x_{2} = A \vec x_{1} = A^{2} \vec x_{0} \\
\vec x_{3} = A \vec x_{2} = A^{3} \vec x_{0} \\
\vdots
\end{array}
$$So in general we have $$
\vec x_{n} = A^{n} \vec x_{0}
$$
### Computing matrix power.
Now our problem becomes, how to compute the power of a square matrix. And we know this is easy if our matrix is diagonalizable.
Here $A$ has characteristic polynomial $$
p_{A}(t) = \det (A-t I) = \det \begin{pmatrix}-t & 1\\1 & 1-t\end{pmatrix} = t^{2}-t-1
$$And its eigenvalues can be found, using quadratic formula, say $$
\lambda = \frac{1 \pm \sqrt{5}}{2}
$$Since we get 2 distinct eigenvalues, and $A$ is $2\times 2$, our matrix $A$ is diagonalizable with diagonalization $A = PDP^{-1}$ for some invertible $P$ and diagonal $$
D = \begin{pmatrix}\frac{1+\sqrt{5}}{2} \\
& \frac{1-\sqrt{5}}{2}\end{pmatrix} = \begin{pmatrix}\lambda_{1}\ & \\ & \lambda_{2}\end{pmatrix}.
$$For simplicity, let us denote the two eigenvalues as $\lambda_{1} = \frac{1+\sqrt{5}}{2}$ and $\lambda_{2}=\frac{1-\sqrt{5}}{2}$.
So we have $$
\begin{align*}
\vec x_{n} & = A^{n}\vec x_{0} \\
& = PD^{n}P^{-1}\vec x_{0} \\
& =P\begin{pmatrix}\lambda_{1} \\ & \lambda_{2}\end{pmatrix}^{n} P^{-1}\vec x_{0}\\
\implies \vec x_{n} & = P \begin{pmatrix}\lambda_{1}^{n} & \\ & \lambda_{2}^{n}\end{pmatrix}P^{-1}\vec x_{0}
\end{align*}
$$
Now we could continue to determine $P$, but it is not necessary, because what we want is the term $a_{n}$, which is the first coefficient of $\vec x_{n} = \begin{pmatrix}a_{n}\\a_{n+1}\end{pmatrix}$, and we can use initial conditions to help us.
### Determining the closed form expression of $a_{n}$ using undetermined coefficients and initial values.
Let us look at our expression $$
\vec x_{n} = \begin{pmatrix}a_{n}\\a_{n+1}\end{pmatrix} = P\begin{pmatrix}\lambda_{1}^{n}\\ & \lambda_{2}^{n}\end{pmatrix}P^{-1}\vec x_{0},
$$we note that we only need the first entry of this vector. The matrix $P$ is $2\times 2$ with four entries that we didn't determine, and $P^{-1}\vec x_{0}$ is some $2\times 1$ vector that we didn't determine either. So let us just give them some temporary coefficients, so $$
\begin{align*}
\vec x_{n} = \begin{pmatrix}a_{n}\\a_{n+1}\end{pmatrix} & = \underbrace{\begin{pmatrix}a & b\\c & d\end{pmatrix} }_{P}\begin{pmatrix}\lambda_{1}^{n}\\ & \lambda_{2}^{n}\end{pmatrix} \underbrace{\begin{pmatrix}e\\f\end{pmatrix}}_{P^{-1}\vec x_{0}} \\
& = \begin{pmatrix}a & b\\c & d\end{pmatrix} \begin{pmatrix}e \lambda_{1}^{n} \\ f \lambda_{2}^{n}\end{pmatrix} \\
\implies\begin{pmatrix}a_{n}\\\ast \end{pmatrix}&= \begin{pmatrix}ae\lambda_{1}^{n} + b f \lambda_{2}^{n} \\ \ast\end{pmatrix}
\end{align*}
$$Here $\ast$ denotes some junk that we don't care about nor need. Now the product $ae$ and $b f$ are just some constants, so we see that $$
a_{n} = C_{1} \lambda_{1}^{n} + C_{2} \lambda_{2}^{n}
$$for some constants $C_{1}$ and $C_{2}$. This is the _general solution_ of $a_{n}$, amazing! (For those who dabbled with differential equations, does this remind you of anything?)
Now to determine the constants $C_{1},C_{2}$, we can use our initial values $a_{0}$ and $a_{1}$. Since in this case we are given $a_{0} = 0$ and $a_{1} =1$, so we have $$
\begin{array}{}
a_{0} = C_{1}\lambda_{1}^{0}+C_{2}\lambda_{2}^{0} = C_{1} + C_{2} = 0 \\
a_{1} = C_{1}\lambda_{1}^{1}+C_{2}\lambda_{2}^{1} = C_{1}\lambda_{1} + C_{2} \lambda_{2} = 1
\end{array}
$$
This gives a system of linear equations for $C_{1}$ and $C_{2}$! Pretty neat that we started with linear algebra, and ended with linear algebra. Using the values $\lambda_{1} = \frac{1+\sqrt{5}}{2}$ and $\lambda_{2} = \frac{1-\sqrt{5}}{2}$ we can solve this system for $C_{1}$ and $C_{2}$ and get $$
C_{1} = \frac{1}{\sqrt{5}}, C_{2} = -\frac{1}{\sqrt{5}}
$$By now, I trust that I can leave you to work out the details of this calculation.
So putting everything together, we finally have a _closed form formula_ for the Fibonacci sequence $(a_{n})_{n=0}^{\infty}$ satisfying $a_{0} =0, a_{1}=1$, and $a_{n+2} = a_{n}+a_{n+1}$, for $n\ge 0$, where $$ \color{blue}
a_{n} = \frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right)^{n} - \frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2} \right)^{n}.
$$Amazing isn't it! Try using a calculator and put in some integer values of $n$ to see if it agrees with the table of values above!
For instance, using the value $n = 1000$ and a calculator we can estimate $$
a_{1000} \approx 4.3 \times 10^{208}.
$$So $a_{1000}$ is a $208+1 = 209$ digit number that starts with a $4$.
Remark. There is nothing special about $a_{0} = 0$ and $a_{1} = 1$. We can easily change the initial values to get a different sequence. So be careful!
### Asymptotic relation.
Now we can even go further and simplify it in the asymptotic limit. Notice that $2 < \sqrt{5} < 3$, so we have $$
-\frac{1}{2} < \lambda_{2} = \frac{1-\sqrt{5}}{2} < -1.
$$In other words, $|\lambda_{2}| < 1$. So in the limit $\lambda_{2}^n \to 0$. Hence our expression $$
a_{n} = C_{1} \lambda_{1}^{n} + C_{2} \lambda
^{n} \sim C_{1}\lambda_{1}^{n}$$That is, we have the asymptotic relation $$ \color{blue}
a_{n} \sim \frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2} \right)^{n},
$$which we see has a geometric (exponential) growth.
In general, you should compare the sizes of the base $\lambda_{1}$ and $\lambda_{2}$ to see which one has a more dominating effect.
## A summary.
In general, if we have a $k$-th order linear recurrence for the sequence $(a_{n})_{n=0}^{\infty}$, satisfying some recurrence relation $$
a_{n+k} = c_{0} a_{n} + c_{1} a_{n+1} +\cdots + c_{k-1} a_{n+k-1},
$$ then consider the sequence of vectors $$
\vec x_{n} = \begin{pmatrix} a_{n} \\ a_{n+1}\\\vdots\\a_{n+k-1}\end{pmatrix}
$$Then notice we have $$
\begin{align*}
\vec x_{n+1} &= \begin{pmatrix}a_{n+1}\\a_{n+2}\\\vdots\\a_{n+k}\end{pmatrix} = \begin{pmatrix}a_{n+1}\\a_{n+2}\\\vdots\\ c_{0} a_{n} + c_{1} a_{n+1} +\cdots + c_{k-1} a_{n+k-1}\end{pmatrix} \\
&= \begin{pmatrix}0 & 1\\0 & 0 & 1\\ & & & \ddots \\ & & & & 1\\ c_{0} & c_{1} & c_{2} & \cdots & c_{k-1} \end{pmatrix} \begin{pmatrix}a_{n}\\a_{n+1}\\a_{n+2}\\\vdots\\a_{n+k-1}\end{pmatrix}
\end{align*}
$$
So we would have the matrix relation between $\vec x_{n+1} = A \vec x_{n}$ for some $k\times k$ matrix $A$ such that $$
A = \begin{pmatrix}0 & 1\\0 & 0 & 1\\ & & & \ddots \\ & & & & 1\\ c_{0} & c_{1} & c_{2} & \cdots & c_{k-1} \end{pmatrix}
$$This matrix $A$ has a _superdiagonal_ of $1$'s, and the bottom row records the coefficients of the linear recurrence. I don't necessarily recommend you memorizing this form, however this type of matrices are called _companion matrices_, and they turn out to be important in the theory of canonical forms in linear algebra. You should nevertheless be able to construct it from the given linear recurrence from scratch.
Now, since we have $$
\vec x_{n} = A^{n} \vec x_{0}
$$
we can compute the matrix power of $A$ by diagonalizing $A$ as $PDP^{-1}$, if $A$ is diagonalizable.
And finally, solve the first entry $a_{n}$ in $\vec x_{n} = A^{n}\vec x_{0} = PD^{n}P^{-1}\vec x_{0}$ using the method of undetermined coefficients. Using the given initial values, $a_{0},a_{1},\ldots,a_{k-1}$, we can finally solve for a closed form formula of $a_{n}$. Done-zo!
Remark. If the matrix $A$ is not diagonalizable then the matrix power $A^{n}$ is _a bit_ more involved to compute. Typically we would use another triangular canonical form that $A$ is similar to called _Jordan canonical forms_. In this case $A = PJP^{-1}$ for some special kind of matrices $J$ called Jordan matrices. The powers of $J$ is still manageable to calculate, but not as easy as in the diagonal case. I hope one day in your near future you learn more about it, in a second course of linear algebra.